

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/blog/img/favicon.png">
  <link rel="icon" type="image/png" href="/blog/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#fff">
  <meta name="description" content="その時を待つよ">
  <meta name="author" content="Isshiki_Hugh">
  <meta name="keywords" content="">
  <title>algotithm-树链剖分 - Isshiki&#39;sBlog</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/blog/lib/hint/hint.min.css" />

  
    
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atom-one-dark.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_6peoq002giu.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/blog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/blog/js/utils.js" ></script>
  <script  src="/blog/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.0.2"></head>


<body>
  <header style="height: 75vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/blog/">&nbsp;<strong>Isshiki修のBlog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/blog/img/default.JPG') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2020-08-19 21:05" pubdate>
      2020年8月19日 晚上
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      81
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">algotithm-树链剖分</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：1 年前
                
              </p>
            
            <div class="markdown-body" id="post-body">
              <h2 id="0-x-前言"><a href="#0-x-前言" class="headerlink" title="[0.x]前言"></a>[0.x]前言</h2><blockquote>
<p>树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。<br>具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。<br>──OI Wiki</p>
</blockquote>
<a id="more"></a>
<h2 id="1-x-轻重链剖分"><a href="#1-x-轻重链剖分" class="headerlink" title="[1.x] 轻重链剖分"></a>[1.x] 轻重链剖分</h2><h3 id="1-1-x-前置概念"><a href="#1-1-x-前置概念" class="headerlink" title="[1.1.x]前置概念"></a>[1.1.x]前置概念</h3><ul>
<li><strong>重儿子</strong>：对于一个节点，它的儿子中最大的一个儿子为重儿子（子树最大的儿子）</li>
<li><strong>轻儿子</strong>：除了重儿子的其他儿子</li>
<li><strong>重边</strong>：连接重儿子的边</li>
<li><strong>轻边</strong>：除了重边的边</li>
<li><strong>重链</strong>：把1个轻儿子和相邻重儿子连起来的链，即一个重链总是以轻儿子或者根重儿子为头的重儿子串</li>
</ul>
<h3 id="1-2-x-预处理"><a href="#1-2-x-预处理" class="headerlink" title="[1.2.x]预处理"></a>[1.2.x]预处理</h3><p>我们进行两次<code>dfs</code>，分别维护这些东西</p>
<h4 id="1-2-1-x-第一次dfs"><a href="#1-2-1-x-第一次dfs" class="headerlink" title="[1.2.1.x]第一次dfs"></a>[1.2.1.x]第一次dfs</h4><p>第一次<code>dfs</code>主要是确定重儿子，为第二次<code>dfs</code>做准备，顺便处理可以一次性处理的东西。</p>
<ul>
<li><code>dep[i]</code>节点<code>i</code>的深度</li>
<li><code>fa[i]</code>节点<code>i</code>的父亲</li>
<li><code>son[i]</code>节点<code>i</code>的重儿子</li>
<li><code>size[i]</code>节点<code>i</code>为根的子树大小</li>
</ul>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs1</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> father)</span></span>&#123;
    size[now] = <span class="hljs-number">1</span> , deep[now] = deep[father] + <span class="hljs-number">1</span> , fa[now] = father;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(ver[i] == fa[now]) <span class="hljs-keyword">continue</span>;
        dfs1(ver[i],now);
        size[now] += size[ ver[i] ];
        son[now] = size[ son[now] ] &gt; size[ ver[i] ] ? son[now] : ver[i]; <span class="hljs-comment">// 更新重儿子</span>
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;</code></pre></div>
<h4 id="1-2-2-x-第二次dfs"><a href="#1-2-2-x-第二次dfs" class="headerlink" title="[1.2.2.x]第二次dfs"></a>[1.2.2.x]第二次dfs</h4><p>第二次<code>dfs</code>是在根据已经得到的重儿子来确定一个特别的<code>dfs</code>序，来维护一些性质</p>
<p>这个<code>dfs</code>序号的特别要求是：先走重儿子，这样能保证重儿子链的<code>dfs</code>序是连续的</p>
<ul>
<li><code>top[i]</code>节点<code>i</code>所在的重链头</li>
<li><code>id[i]</code>节点<code>i</code>的<code>dfs</code>序号</li>
<li><code>b[id[i]]</code>通过节点<code>i</code>的<code>dfs</code>序索引<code>a[i]</code></li>
</ul>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs2</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> toper)</span></span>&#123;
    id[now] = ++id[<span class="hljs-number">0</span>] , top[now] = toper , b[id[<span class="hljs-number">0</span>]] = a[now];
    <span class="hljs-keyword">if</span>(!son[now]) <span class="hljs-keyword">return</span>; <span class="hljs-comment">// 没有重儿子即叶子节点</span>
    dfs2(son[now],toper); <span class="hljs-comment">// 重儿子先走</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(id[ ver[i] ]) <span class="hljs-keyword">continue</span>;
        dfs2(ver[i],ver[i]);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;</code></pre></div>
<h3 id="1-3-x-线段树维护"><a href="#1-3-x-线段树维护" class="headerlink" title="[1.3.x]线段树维护"></a>[1.3.x]线段树维护</h3><p>经过预处理后，我们可以发现，所有在同一个重链中的重儿子的<code>dfs</code>序是连续的，同时，还有一个性质，以<code>i</code>为根的子树上所有的点的<code>dfs</code>序都在<code>[id[i],id[i]+size[i]-1]</code>中。因此我们可以以<code>dfs</code>序为索引建立线段树</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-keyword">int</span> TOT;
<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    <span class="hljs-keyword">int</span> l,r;
    ll sum,tag;
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dis</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> r-l+<span class="hljs-number">1</span>;&#125;
    node * ls, * rs;
&#125;Tree[<span class="hljs-number">4</span>*N];

<span class="hljs-function"><span class="hljs-keyword">inline</span> node * <span class="hljs-title">create</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> &amp;Tree[++TOT];&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(node * cur)</span></span>&#123;
    cur-&gt;ls-&gt;sum += cur-&gt;tag * cur-&gt;ls-&gt;dis(), cur-&gt;ls-&gt;sum %= p;
    cur-&gt;ls-&gt;tag += cur-&gt;tag , cur-&gt;ls-&gt;tag %= p;
    cur-&gt;rs-&gt;sum += cur-&gt;tag * cur-&gt;rs-&gt;dis(), cur-&gt;rs-&gt;sum %= p;
    cur-&gt;rs-&gt;tag += cur-&gt;tag , cur-&gt;rs-&gt;tag %= p;
    cur-&gt;tag = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushup</span><span class="hljs-params">(node * cur)</span></span>&#123;cur-&gt;sum = (cur-&gt;ls-&gt;sum + cur-&gt;rs-&gt;sum)%p;&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>&#123;
    cur-&gt;l = l , cur-&gt;r = r , cur-&gt;sum = cur-&gt;tag = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(cur-&gt;l == cur-&gt;r)&#123;cur-&gt;sum = b[l];<span class="hljs-keyword">return</span>;&#125;
    <span class="hljs-keyword">int</span> mid = (l+r)&gt;&gt;<span class="hljs-number">1</span>;
    cur-&gt;ls = create() , cur-&gt;rs = create();
    build(cur-&gt;ls,l,mid) , build(cur-&gt;rs,mid+<span class="hljs-number">1</span>,r);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> x)</span></span>&#123;
    <span class="hljs-keyword">if</span>(l &gt; cur-&gt;r || r &lt; cur-&gt;l) <span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(l &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= r)&#123;
        cur-&gt;sum += x * cur-&gt;dis() % p , cur-&gt;sum %= p , cur-&gt;tag += x;
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">if</span>(cur-&gt;l == cur-&gt;r) <span class="hljs-keyword">return</span>;
    pushdown(cur);
    <span class="hljs-keyword">if</span>(l &lt;= cur-&gt;ls-&gt;r) edit(cur-&gt;ls,l,r,x);
    <span class="hljs-keyword">if</span>(r &gt;= cur-&gt;rs-&gt;l) edit(cur-&gt;rs,l,r,x);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">query</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>&#123;
    <span class="hljs-keyword">if</span>(l &gt; cur-&gt;r || r &lt; cur-&gt;l) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(l &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= r) <span class="hljs-keyword">return</span> cur-&gt;sum;
    pushdown(cur);
    <span class="hljs-keyword">return</span> (query(cur-&gt;ls,l,r) + query(cur-&gt;rs,l,r))%p;
&#125;</code></pre></div>
<h3 id="1-4-x-实现"><a href="#1-4-x-实现" class="headerlink" title="[1.4.x]实现"></a>[1.4.x]实现</h3><h4 id="1-4-1-x-链上修改"><a href="#1-4-1-x-链上修改" class="headerlink" title="[1.4.1.x]链上修改"></a>[1.4.1.x]链上修改</h4><p>首先这里肯定要用到线段树的区间修改，怎样增加效率呢。首先我们已经有了所有重链的序号连续，那自然通过<code>top[i]</code>不断向上跳，类似于树上倍增<code>LCA</code>，不断上跳直到两个点在同一个重链中。</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit_chain</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//把x到y都加上z</span>
    <span class="hljs-keyword">while</span>(top[x] != top[y])&#123;
        <span class="hljs-keyword">if</span>(deep[ top[x] ] &lt; deep[ top[y] ]) <span class="hljs-built_in">std</span>::swap(x,y);
        edit(cur,id[top[x]],id[x],z);
        x = fa[ top[x] ];
    &#125;
    <span class="hljs-keyword">if</span>(id[x] &gt; id[y]) <span class="hljs-built_in">std</span>::swap(x,y);
    edit(cur,id[x],id[y],z);
    <span class="hljs-keyword">return</span>;
&#125;</code></pre></div>
<p>链上查询和链上修改同理。<br><div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">query_chain</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//查询x到y的和</span>
    ll ans = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(top[x] != top[y])&#123;
        <span class="hljs-keyword">if</span>(deep[ top[x] ] &lt; deep[ top[y] ]) <span class="hljs-built_in">std</span>::swap(x,y);
        ans += query(cur,id[top[x]],id[x]) , ans %= p;
        x = fa[top[x]];
    &#125;
    <span class="hljs-keyword">if</span>(id[x] &gt; id[y]) <span class="hljs-built_in">std</span>::swap(x,y);
    ans += query(cur,id[x],id[y]) , ans %= p;
    <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span>;
&#125;</code></pre></div><br>树上修改和查询就更简单了，直接操作<code>[id[i],id[i]+size[i]-1]</code>就行</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit_tree</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//给x的子树都加上z</span>
    edit(cur,id[x],id[x]+size[x]<span class="hljs-number">-1</span>,z);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">query_tree</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//查询x的子树和</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; query(cur,id[x],id[x]+size[x]<span class="hljs-number">-1</span>) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span>;
&#125;</code></pre></div>
<p>区间最值的维护和区间和的维护基本上类似，可以参考相关题目第二题的代码。</p>
<h3 id="1-5-x-相关题目"><a href="#1-5-x-相关题目" class="headerlink" title="[1.5.x]相关题目"></a>[1.5.x]相关题目</h3><p><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3384">P3384 【模板】轻重链剖分</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;bitset&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register int i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register int i = (a);i &gt;= (b);--i)  </span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N = <span class="hljs-number">1e5</span>+<span class="hljs-number">5</span>;
<span class="hljs-keyword">int</span> n,m,root,p,a[<span class="hljs-number">2</span>*N],b[<span class="hljs-number">2</span>*N],x,y,z,opt;
<span class="hljs-keyword">int</span> head[<span class="hljs-number">2</span>*N],next[<span class="hljs-number">2</span>*N],ver[<span class="hljs-number">2</span>*N],tot;
<span class="hljs-keyword">int</span> fa[<span class="hljs-number">2</span>*N],top[<span class="hljs-number">2</span>*N],deep[<span class="hljs-number">2</span>*N],son[<span class="hljs-number">2</span>*N],size[<span class="hljs-number">2</span>*N],id[<span class="hljs-number">2</span>*N];

<span class="hljs-comment">//------------------------------------------------------</span>

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">link</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span></span>&#123;ver[++tot] = y , next[tot] = head[x] , head[x] = tot;&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs1</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> father)</span></span>&#123;
    size[now] = <span class="hljs-number">1</span> , deep[now] = deep[father] + <span class="hljs-number">1</span> , fa[now] = father;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(ver[i] == fa[now]) <span class="hljs-keyword">continue</span>;
        dfs1(ver[i],now);
        size[now] += size[ ver[i] ];
        son[now] = size[ son[now] ] &gt; size[ ver[i] ] ? son[now] : ver[i]; <span class="hljs-comment">// 更新重儿子</span>
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs2</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> toper)</span></span>&#123;
    id[now] = ++id[<span class="hljs-number">0</span>] , top[now] = toper , b[id[<span class="hljs-number">0</span>]] = a[now];
    <span class="hljs-keyword">if</span>(!son[now]) <span class="hljs-keyword">return</span>; <span class="hljs-comment">// 没有重儿子即叶子节点</span>
    dfs2(son[now],toper); <span class="hljs-comment">// 重儿子先走</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(id[ ver[i] ]) <span class="hljs-keyword">continue</span>;
        dfs2(ver[i],ver[i]);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-comment">//------------------------------------------------------</span>

<span class="hljs-keyword">int</span> TOT;
<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    <span class="hljs-keyword">int</span> l,r;
    ll sum,tag;
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dis</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> r-l+<span class="hljs-number">1</span>;&#125;
    node * ls, * rs;
&#125;Tree[<span class="hljs-number">4</span>*N];

<span class="hljs-function"><span class="hljs-keyword">inline</span> node * <span class="hljs-title">create</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> &amp;Tree[++TOT];&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(node * cur)</span></span>&#123;
    cur-&gt;ls-&gt;sum += cur-&gt;tag * cur-&gt;ls-&gt;dis(), cur-&gt;ls-&gt;sum %= p;
    cur-&gt;ls-&gt;tag += cur-&gt;tag , cur-&gt;ls-&gt;tag %= p;
    cur-&gt;rs-&gt;sum += cur-&gt;tag * cur-&gt;rs-&gt;dis(), cur-&gt;rs-&gt;sum %= p;
    cur-&gt;rs-&gt;tag += cur-&gt;tag , cur-&gt;rs-&gt;tag %= p;
    cur-&gt;tag = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushup</span><span class="hljs-params">(node * cur)</span></span>&#123;cur-&gt;sum = (cur-&gt;ls-&gt;sum + cur-&gt;rs-&gt;sum)%p;&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>&#123;
    cur-&gt;l = l , cur-&gt;r = r , cur-&gt;sum = cur-&gt;tag = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(cur-&gt;l == cur-&gt;r)&#123;cur-&gt;sum = b[l];<span class="hljs-keyword">return</span>;&#125;
    <span class="hljs-keyword">int</span> mid = (l+r)&gt;&gt;<span class="hljs-number">1</span>;
    cur-&gt;ls = create() , cur-&gt;rs = create();
    build(cur-&gt;ls,l,mid) , build(cur-&gt;rs,mid+<span class="hljs-number">1</span>,r);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> x)</span></span>&#123;
    <span class="hljs-keyword">if</span>(l &gt; cur-&gt;r || r &lt; cur-&gt;l) <span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(l &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= r)&#123;
        cur-&gt;sum += x * cur-&gt;dis() % p , cur-&gt;sum %= p , cur-&gt;tag += x;
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">if</span>(cur-&gt;l == cur-&gt;r) <span class="hljs-keyword">return</span>;
    pushdown(cur);
    <span class="hljs-keyword">if</span>(l &lt;= cur-&gt;ls-&gt;r) edit(cur-&gt;ls,l,r,x);
    <span class="hljs-keyword">if</span>(r &gt;= cur-&gt;rs-&gt;l) edit(cur-&gt;rs,l,r,x);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">query</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>&#123;
    <span class="hljs-keyword">if</span>(l &gt; cur-&gt;r || r &lt; cur-&gt;l) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(l &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= r) <span class="hljs-keyword">return</span> cur-&gt;sum;
    pushdown(cur);
    <span class="hljs-keyword">return</span> (query(cur-&gt;ls,l,r) + query(cur-&gt;rs,l,r))%p;
&#125;

<span class="hljs-comment">//------------------------------------------------------</span>

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit_chain</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//把x到y都加上z</span>
    <span class="hljs-keyword">while</span>(top[x] != top[y])&#123;
        <span class="hljs-keyword">if</span>(deep[ top[x] ] &lt; deep[ top[y] ]) <span class="hljs-built_in">std</span>::swap(x,y);
        edit(cur,id[top[x]],id[x],z);
        x = fa[ top[x] ];
    &#125;
    <span class="hljs-keyword">if</span>(id[x] &gt; id[y]) <span class="hljs-built_in">std</span>::swap(x,y);
    edit(cur,id[x],id[y],z);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">query_chain</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//查询x到y的和</span>
    ll ans = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(top[x] != top[y])&#123;
        <span class="hljs-keyword">if</span>(deep[ top[x] ] &lt; deep[ top[y] ]) <span class="hljs-built_in">std</span>::swap(x,y);
        ans += query(cur,id[top[x]],id[x]) , ans %= p;
        x = fa[top[x]];
    &#125;
    <span class="hljs-keyword">if</span>(id[x] &gt; id[y]) <span class="hljs-built_in">std</span>::swap(x,y);
    ans += query(cur,id[x],id[y]) , ans %= p;
    <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit_tree</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//给x的子树都加上z</span>
    edit(cur,id[x],id[x]+size[x]<span class="hljs-number">-1</span>,z);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">query_tree</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-comment">//查询x的子树和</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; query(cur,id[x],id[x]+size[x]<span class="hljs-number">-1</span>) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-comment">//------------------------------------------------------</span>

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m &gt;&gt; root &gt;&gt; p;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    rep(i,<span class="hljs-number">1</span>,n<span class="hljs-number">-1</span>)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; x &gt;&gt; y;
        link(x,y) , link(y,x);
    &#125;
    fa[root] = <span class="hljs-number">0</span> , deep[fa[root]] = <span class="hljs-number">0</span>;
    dfs1(root,<span class="hljs-number">0</span>);
    dfs2(root,root);
    node * Root = create();
    build(Root,<span class="hljs-number">1</span>,n);
    <span class="hljs-keyword">while</span>(m--)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; opt;
        <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">1</span>)&#123;<span class="hljs-comment">//链改</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; x &gt;&gt; y &gt;&gt; z;
            z %= p;
            edit_chain(Root);
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">2</span>)&#123;<span class="hljs-comment">//链查</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; x &gt;&gt; y;
            query_chain(Root);
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">3</span>)&#123;<span class="hljs-comment">//树改</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; x &gt;&gt; z;
            z %= p;
            edit_tree(Root);
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">4</span>)&#123;<span class="hljs-comment">//树查</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; x;
            query_tree(Root);
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P2590">P2590 [ZJOI2008]树的统计</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;bitset&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register int i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register int i = (a);i &gt;= (b);--i) </span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> mkp std::make_pair</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">bool</span> <span class="hljs-title">cmp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span></span>&#123;<span class="hljs-keyword">return</span> x &lt; y;&#125;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> inf = <span class="hljs-number">1e9</span>+<span class="hljs-number">9</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N = <span class="hljs-number">1e6</span>+<span class="hljs-number">9</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">double</span> eps = <span class="hljs-number">1e-7</span>;
<span class="hljs-keyword">int</span> _,n,m,a[<span class="hljs-number">2</span>*N],u,v;
<span class="hljs-built_in">string</span> str;

<span class="hljs-comment">//----------------------------</span>

<span class="hljs-keyword">int</span> head[<span class="hljs-number">2</span>*N],next[<span class="hljs-number">2</span>*N],ver[<span class="hljs-number">2</span>*N],tot;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">link</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span></span>&#123;ver[++tot] = y , next[tot] = head[x] , head[x] = tot;&#125;

<span class="hljs-comment">//----------------------------</span>

<span class="hljs-keyword">int</span> fa[<span class="hljs-number">2</span>*N],top[<span class="hljs-number">2</span>*N],son[<span class="hljs-number">2</span>*N],size[<span class="hljs-number">2</span>*N],deep[<span class="hljs-number">2</span>*N],id[<span class="hljs-number">2</span>*N],b[<span class="hljs-number">2</span>*N];

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs1</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> fathter)</span></span>&#123;
    fa[now] = fathter , deep[now] = deep[fathter] + <span class="hljs-number">1</span> , size[now] = <span class="hljs-number">1</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(ver[i] == fathter) <span class="hljs-keyword">continue</span>;
        dfs1(ver[i],now);
        size[now] += size[ ver[i] ];
        son[now] = size[ son[now] ] &gt; size[ son[ver[i]] ] ? son[now] : ver[i];
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs2</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> toper)</span></span>&#123;
    id[now] = ++id[<span class="hljs-number">0</span>] , b[ id[<span class="hljs-number">0</span>] ] = a[now] , top[now] = toper;
    <span class="hljs-keyword">if</span>(!son[now]) <span class="hljs-keyword">return</span>;
    dfs2(son[now],toper);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(id[ ver[i] ]) <span class="hljs-keyword">continue</span>;
        dfs2(ver[i],ver[i]);
    &#125;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-comment">//----------------------------</span>

<span class="hljs-keyword">int</span> TOT;
<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    <span class="hljs-keyword">int</span> l,r,sum,max;
    node * ls , * rs;
&#125;Tree[<span class="hljs-number">4</span>*N];

<span class="hljs-function"><span class="hljs-keyword">inline</span> node * <span class="hljs-title">create</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> &amp;Tree[++TOT];&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushup</span><span class="hljs-params">(node * cur)</span></span>&#123;cur-&gt;sum = cur-&gt;ls-&gt;sum + cur-&gt;rs-&gt;sum , cur-&gt;max = <span class="hljs-built_in">std</span>::max(cur-&gt;ls-&gt;max,cur-&gt;rs-&gt;max);&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>&#123;
    cur-&gt;l = l , cur-&gt;r = r , cur-&gt;sum = cur-&gt;max = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(l == r)&#123;
        cur-&gt;sum = cur-&gt;max = b[l];
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">int</span> mid = (l+r) &gt;&gt; <span class="hljs-number">1</span>;
    cur-&gt;ls = create() , cur-&gt;rs = create();
    build(cur-&gt;ls,l,mid) , build(cur-&gt;rs,mid+<span class="hljs-number">1</span>,r);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(cur-&gt;l == cur-&gt;r)&#123;
        cur-&gt;sum = cur-&gt;max = v;
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">if</span>(u &lt;= cur-&gt;ls-&gt;r) edit(cur-&gt;ls);
    <span class="hljs-keyword">if</span>(cur-&gt;rs-&gt;l &lt;= u) edit(cur-&gt;rs);
    pushup(cur);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">query_max</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(cur-&gt;r &lt; u || v &lt; cur-&gt;l) <span class="hljs-keyword">return</span> -inf;
    <span class="hljs-keyword">if</span>(u &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= v) <span class="hljs-keyword">return</span> cur-&gt;max;
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">std</span>::max(query_max(cur-&gt;ls),query_max(cur-&gt;rs));
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">int</span> <span class="hljs-title">query_sum</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(cur-&gt;r &lt; u || v &lt; cur-&gt;l) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(u &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= v) <span class="hljs-keyword">return</span> cur-&gt;sum;
    <span class="hljs-keyword">return</span> query_sum(cur-&gt;ls) + query_sum(cur-&gt;rs);
&#125;

<span class="hljs-comment">//----------------------------</span>

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    rep(i,<span class="hljs-number">1</span>,n<span class="hljs-number">-1</span>)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; u &gt;&gt; v;
        link(u,v) , link(v,u);
    &#125;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];

    <span class="hljs-comment">//----------------------------</span>

    dfs1(<span class="hljs-number">1</span>,<span class="hljs-number">1</span>) , dfs2(<span class="hljs-number">1</span>,<span class="hljs-number">1</span>);
    node * root = create();
    build(root,<span class="hljs-number">1</span>,n);

    <span class="hljs-comment">//----------------------------</span>

    <span class="hljs-built_in">cin</span> &gt;&gt; m;
    <span class="hljs-keyword">while</span>(m--)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; str &gt;&gt; u &gt;&gt; v;
        <span class="hljs-keyword">if</span>(str == <span class="hljs-string">&quot;CHANGE&quot;</span>)&#123;
            u = id[u];
            edit(root);
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(str == <span class="hljs-string">&quot;QMAX&quot;</span>)&#123;
            <span class="hljs-keyword">int</span> x = u , y = v , ans = -inf;
            <span class="hljs-keyword">while</span>(top[x] != top[y])&#123;
                <span class="hljs-keyword">if</span>(deep[ top[x] ] &lt; deep[ top[y] ]) <span class="hljs-built_in">std</span>::swap(x,y);
                u = id[ top[x] ] , v = id[x] , x = fa[ top[x] ] , ans = <span class="hljs-built_in">std</span>::max(ans,query_max(root));
            &#125;
            <span class="hljs-keyword">if</span>(id[x] &gt; id[y]) <span class="hljs-built_in">std</span>::swap(x,y);
            u = id[x] , v = id[y] , ans = <span class="hljs-built_in">std</span>::max(ans,query_max(root));
            <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(str == <span class="hljs-string">&quot;QSUM&quot;</span>)&#123;
            <span class="hljs-keyword">int</span> x = u , y = v , ans = <span class="hljs-number">0</span>;
            <span class="hljs-keyword">while</span>(top[x] != top[y])&#123;
                <span class="hljs-keyword">if</span>(deep[ top[x] ] &lt; deep[ top[y] ]) <span class="hljs-built_in">std</span>::swap(x,y);
                u = id[ top[x] ] , v = id[x] , x = fa[ top[x] ] , ans += query_sum(root);
            &#125;
            <span class="hljs-keyword">if</span>(id[x] &gt; id[y]) <span class="hljs-built_in">std</span>::swap(x,y);
            u = id[x] , v = id[y] , ans += query_sum(root);
            <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<p><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3178">P3178 [HAOI2015]树上操作</a></strong></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;bitset&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register int i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register int i = (a);i &gt;= (b);--i) </span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> mkp std::make_pair</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">bool</span> <span class="hljs-title">cmp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span></span>&#123;<span class="hljs-keyword">return</span> x &lt; y;&#125;

<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> N = <span class="hljs-number">1e5</span>+<span class="hljs-number">9</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> inf = <span class="hljs-number">1e9</span>+<span class="hljs-number">9</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">double</span> eps = <span class="hljs-number">1e-7</span>;
<span class="hljs-keyword">int</span> _,n,m,a[<span class="hljs-number">2</span>*N],opt,u,v,w;
<span class="hljs-comment">//----------------------------</span>
<span class="hljs-keyword">int</span> head[<span class="hljs-number">2</span>*N],ver[<span class="hljs-number">2</span>*N],next[<span class="hljs-number">2</span>*N],tot;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">link</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span></span>&#123;ver[++tot] = y , next[tot] = head[x] , head[x] = tot;&#125;
<span class="hljs-comment">//----------------------------</span>
<span class="hljs-keyword">int</span> fa[<span class="hljs-number">2</span>*N],top[<span class="hljs-number">2</span>*N],deep[<span class="hljs-number">2</span>*N],size[<span class="hljs-number">2</span>*N],son[<span class="hljs-number">2</span>*N],id[<span class="hljs-number">2</span>*N],b[<span class="hljs-number">2</span>*N];

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs1</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> father)</span></span>&#123;
    fa[now] = father , deep[now] = deep[father] + <span class="hljs-number">1</span> , size[now] = <span class="hljs-number">1</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(ver[i] == father) <span class="hljs-keyword">continue</span>;
        dfs1(ver[i],now);
        size[now] += size[ ver[i] ];
        son[now] = size[ son[now] ] &gt; size[ ver[i] ] ? son[now] : ver[i];
    &#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs2</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> toper)</span></span>&#123;
    top[now] = toper , id[now] = ++id[<span class="hljs-number">0</span>] , b[ id[<span class="hljs-number">0</span>] ] = a[now];
    <span class="hljs-keyword">if</span>(!son[now]) <span class="hljs-keyword">return</span>;
    dfs2(son[now],toper);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = head[now];i;i = next[i])&#123;
        <span class="hljs-keyword">if</span>(id[ ver[i] ]) <span class="hljs-keyword">continue</span>;
        dfs2(ver[i],ver[i]);
    &#125;
&#125;
<span class="hljs-comment">//----------------------------</span>
<span class="hljs-keyword">int</span> TOT;
<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span>
    <span class="hljs-keyword">int</span> l,r;
    ll tag,sum;
    node * ls , * rs;
    <span class="hljs-function">ll <span class="hljs-title">dis</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> r-l+<span class="hljs-number">1</span>;&#125;
&#125;Tree[<span class="hljs-number">4</span>*N];

<span class="hljs-function"><span class="hljs-keyword">inline</span> node * <span class="hljs-title">create</span><span class="hljs-params">()</span></span>&#123;<span class="hljs-keyword">return</span> &amp;Tree[++TOT];&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushup</span><span class="hljs-params">(node * cur)</span></span>&#123;cur-&gt;sum = cur-&gt;ls-&gt;sum + cur-&gt;rs-&gt;sum;&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(node * cur)</span></span>&#123;
    cur-&gt;ls-&gt;tag += cur-&gt;tag , cur-&gt;rs-&gt;tag += cur-&gt;tag;
    cur-&gt;ls-&gt;sum += cur-&gt;tag * cur-&gt;ls-&gt;dis();
    cur-&gt;rs-&gt;sum += cur-&gt;tag * cur-&gt;rs-&gt;dis();
    cur-&gt;tag = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(node * cur,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>&#123;
    cur-&gt;l = l , cur-&gt;r = r , cur-&gt;tag = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(l == r)&#123;cur-&gt;sum = b[l];<span class="hljs-keyword">return</span>;&#125;
    <span class="hljs-keyword">int</span> mid = (l+r) &gt;&gt; <span class="hljs-number">1</span>;
    cur-&gt;ls = create() , cur-&gt;rs = create();
    build(cur-&gt;ls,l,mid) , build(cur-&gt;rs,mid+<span class="hljs-number">1</span>,r);
    pushup(cur);
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">edit</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(v &lt; cur-&gt;l || cur-&gt;r &lt; u) <span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(u &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= v)&#123;
        cur-&gt;tag += w , cur-&gt;sum += w * cur-&gt;dis();
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">if</span>(cur-&gt;l == cur-&gt;r) <span class="hljs-keyword">return</span>;
    pushdown(cur);
    <span class="hljs-keyword">if</span>(u &lt;= cur-&gt;ls-&gt;r) edit(cur-&gt;ls);
    <span class="hljs-keyword">if</span>(cur-&gt;rs-&gt;l &lt;= v) edit(cur-&gt;rs);
    pushup(cur);
&#125;

<span class="hljs-function"><span class="hljs-keyword">inline</span> ll <span class="hljs-title">query</span><span class="hljs-params">(node * cur)</span></span>&#123;
    <span class="hljs-keyword">if</span>(v &lt; cur-&gt;l || cur-&gt;r &lt; u) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-keyword">if</span>(u &lt;= cur-&gt;l &amp;&amp; cur-&gt;r &lt;= v) <span class="hljs-keyword">return</span> cur-&gt;sum;
    pushdown(cur);
    <span class="hljs-keyword">return</span> query(cur-&gt;ls) + query(cur-&gt;rs);
&#125;

<span class="hljs-comment">//----------------------------</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    rep(i,<span class="hljs-number">1</span>,n<span class="hljs-number">-1</span>)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; u &gt;&gt; v;
        link(u,v) , link(v,u);
    &#125;
    dfs1(<span class="hljs-number">1</span>,<span class="hljs-number">1</span>) , dfs2(<span class="hljs-number">1</span>,<span class="hljs-number">1</span>);
    node * root = create();
    build(root,<span class="hljs-number">1</span>,n);
    <span class="hljs-keyword">int</span> p,x;
    <span class="hljs-keyword">while</span>(m--)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; opt;
        <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">1</span>)&#123;<span class="hljs-comment">//point edit</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; p &gt;&gt; x;
            u = v = id[p] , w = x;
            edit(root);
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(opt == <span class="hljs-number">2</span>)&#123;<span class="hljs-comment">//tree edit</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; p &gt;&gt; x;
            u = id[p] , v = id[p] + size[p] - <span class="hljs-number">1</span> , w = x;
            edit(root);
        &#125; <span class="hljs-keyword">else</span> &#123;<span class="hljs-comment">//query</span>
            <span class="hljs-built_in">cin</span> &gt;&gt; p;
            ll ans = <span class="hljs-number">0</span>;
            <span class="hljs-keyword">while</span>(top[<span class="hljs-number">1</span>] != top[p])&#123;
                u = id[ top[p] ] , v = id[p];
                ans += query(root);
                p = fa[ top[p] ];
            &#125;
            u = id[<span class="hljs-number">1</span>] , v = id[p];
            <span class="hljs-built_in">cout</span> &lt;&lt; ans + query(root) &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>
    </div>
</div><link rel="stylesheet" href="/blog/css/spoiler.css" type="text/css"><script src="/blog/js/spoiler.js" type="text/javascript" async></script>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/blog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%BF%A1%E5%A5%A5/">信奥</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%B8%93%E9%A2%98/">专题</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E7%BA%BF%E6%AE%B5%E6%A0%91/">线段树</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86/">树链剖分</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">未经允许禁止用于商业用途，转载请标注出处和作者！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/blog/2020/08/22/algHJTtree/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">algorithm-主席树/可持久化线段树</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/blog/2020/08/19/algScanLine/">
                        <span class="hidden-mobile">algorithm-扫描线</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80ODI4NS8yNDc3OQ==">
  <script type="text/javascript">
     (function(d, s) {
         var j, e = d.getElementsByTagName(s)[0];
  
         if (typeof LivereTower === 'function') { return; }
  
         j = d.createElement(s);
         j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
         j.async = true;
  
         e.parentNode.insertBefore(j, e);
     })(document, 'script');
  </script>
  <noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
  </div>
  <!-- City版安装代码已完成 -->
              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <p><center><b>(っ*´Д`)っ㊖ <font color="darkblue">  疯 狂 暗 示  </font>(っ*´Д`)っ㊖</b></center></p><center><img src="https://pic.downk.cc/item/5f3bd3b414195aa59408fb13.png" srcset="/blog/img/loading.gif" width="50%" height="50%"/></center>
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  
    <!-- APlayer 音乐播放器 -->
    <div id="aplayer"></div>
    <script defer src="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.js" ></script>
<link  rel="stylesheet" href="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.css" />
<script type="text/javascript">
  var oldLoadAp = window.onload;
  window.onload = function () {
    oldLoadAp && oldLoadAp();

    new APlayer({
      container: document.getElementById('aplayer'),
      fixed: true,
      autoplay: 'false' === 'true',
      loop: 'all',
      order: 'random',
      theme: '#708090',
      preload: 'none',
      audio: [{"name":"SLEEPWALK","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1417007045.mp3","cover":"/img/cover.jpg"},{"name":"雨き声残响","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1318309030.mp3","cover":"/img/cover.jpg"},{"name":"春を告げる","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1460240705.mp3","cover":"/img/cover.jpg"},{"name":"ベクターフィッシュ","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1445572300.mp3","cover":"/img/cover.jpg"},{"name":"红莲华","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1397590357.mp3","cover":"/img/cover.jpg"},{"name":"横竖撇点折","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1421414775.mp3","cover":"/img/cover.jpg"},{"name":"たぶん","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1464762744.mp3","cover":"/img/cover.jpg"},{"name":"夜に駆ける","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1461930738.mp3","cover":"/img/cover.jpg"},{"name":"Alice","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1431092750.mp3","cover":"/img/cover.jpg"},{"name":"起风了","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1367440424.mp3","cover":"/img/cover.jpg"}]
    });
  }
</script>

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/blog/js/debouncer.js" ></script>
<script  src="/blog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/blog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/blog/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "algotithm-树链剖分&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>





  <script  src="/blog/js/local-search.js" ></script>
  <script>
    var path = "/blog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  














<script src="/blog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/blog/live2dw/assets/assets/hijiki.model.json"},"display":{"superSample":1,"width":150,"height":300,"position":"right","hOffset":0,"vOffset":-20},"mobile":{"show":true,"scale":1},"react":{"opacityDefault":0.7,"opacityOnHover":0.2},"log":false});</script></body>
</html>
